#include <algorithm>
#include<string>
#include<vector>
#include<array>
#include<unordered_map>
#include<algorithm>
#include<limits>
#include <stack>
#include<iostream>
#include<sstream>
#include<deque>
#include <queue>
#define MOD 1000000007

class Solution
{
public:
    int minimumTime(int n, std::vector<std::vector<int>>& relations, std::vector<int>& time)
    {
        std::vector<std::vector<int>> tu(n);
        std::vector<int> du(n, 0);
        int len = relations.size();
        for (int i = 0; i < len; i++)
        {
            tu[relations[i][0] - 1].push_back(relations[i][1] - 1);
            du[relations[i][1] - 1]++;
        }
        std::vector<int> res(n, 0);
        std::queue<int> q;
        for (int i = 0; i < n; i++)
        {
            if (du[i] == 0)
            {
                q.push(i);
                res[i] += time[i];
            }
        }
        int max = 0;
        while (!q.empty())
        {
            int cur = q.front();
            q.pop();
            max = std::max(max, res[cur]);
            for (const auto& x : tu[cur])
            {
                res[x] = std::max(res[x], res[cur]);
                du[x]--;
                if (du[x] == 0)
                {
                    q.push(x);
                    res[x] += time[x];
                }
            }
        }
        return max;
    }
};
